\chapter{Вопрос №12}

Нелинейные рекуррентные соотношения. Числа Каталана.

\section{Числа Каталана}

Назовем правильной скобочной последовательностю из $2n$ скобок ($n$ открывающих и $n$ закрывающих) последовательность, в которой в любом префиксе количество открывающих скобок не меньше количества закрывающих.

Вопрос сколько существует таких правильных скобочных последовательностей из $2n$ скобок? Для решения рассмотрим как выглядят правильные скобочные последовательности: $$ \left( \alpha_1 \right) \alpha_2 $$
Правильная скобочная последовательность всегда начинается с открывающей скобки, между открывающей скобкой и соответствующей ей закрывающей распологается правильная (возможно пустая) скобочная последовательность $\alpha_1$, а после закрывающей скобки располагается опять же правильная (возможно пустая) скобочная последовательность $\alpha_2$.

Так как $\alpha_1$ - правильная скобочная последовательность, то соответствующая начальной закрывающая скобка стоит в четной позиции, отсюда суммируя по всем возможным длинам $\alpha_1$ получаем рекуррентное соотношение:
\begin{equation}
	c_n = \sum_{i=0}^{n-1}c_ic_{n-i-1}
\end{equation}
где $ c_n $ обозначение для числа правильных скобочных последовательностей из $2n$ скобок. Добавим начальные условия:
\[
	c_0 = 1
\]
полученная последовательность чисел называется числами Каталана.

\section{Нелинейные рекуррентные соотношения}

Видно, что числа Каталана описываются нелинейным рекуррентны соотношением, решим его, для этого немного преобразуем выражение и домножим на $x^{n+1}$, а затем просуммируем как обычно:
\[
	\begin{split}
		\sum_{n=0}^{\infty} c_{n+1}x^{n+1} = \sum_{n=0}^{\infty} \left[\sum_{k=0}^n c_kc_{n-k}\right]x^{n+1} \Leftrightarrow f\left(x\right) - c_0 = xf\left(x\right)f\left(x\right)
	\end{split}
\]
справа стояло произведение двух опф умноженное на $x$, чем мы и воспользовались, далее:
\[
	f\left(x\right) = \frac{1\pm\sqrt{1-4x}}{2x}
\]
одно из решени должно быть отброшено, перед тем как мы это сделаем рассмотрим как раскладывается выражение под корнем:
\[
	\begin{split}
		& \left(1-4x\right)^{1/2} = 1 + \sum_{n=1}^{\infty} \frac{1/2\left(1/2-1\right)\left(1/2-2\right)...\left(1/2-n+1\right)}{n!} \left(-4x\right)^n = \\
		& = 1 - \sum_{n=1}^{\infty}\frac{1/2\cdot1/2\cdot3/2\cdot...\cdot\left(n-3/2\right)}{n!} 2^n2^nx^n = 1+\sum_{n=1}^\infty \frac{1\cdot3\cdot5\cdot...\cdot\left(2n-3\right)}{n!}2^nx^n = \\
		& = 1 - 2\sum_{n=1}^{\infty}\frac{\left(2n-2\right)!}{n!\left(n-1\right)!}x^n
	\end{split}
\]
теперь понятно, что правильный знак $-$ в исходной формуле, поэтому получаем:
\[
	\begin{split}
		& \sum_{n=1}^{\infty} \frac{\left(2n-2\right)!}{n\left(n-1\right)!\left(n-1\right)!} x^{n-1}  = \frac{1}{n+1}\sum_{n=0}^{\infty}\frac{2n!}{n!n!}x^n 
	\end{split}
\]
получили замкнутую формулу для чисел Каталана:
\begin{equation}
	c_n = \frac{1}{1+n}\binom{2n}{n}
\end{equation}
